package com.cloud.code.算法.leetCode;

import java.util.ArrayList;

public class LeetCode22 {

    public static void main(String[] args) {

    }

    public ArrayList<String> generateParenthesis(int n) {

        ArrayList<String> res = new ArrayList<>();

        int left = 0;
        int rigth = 0;

        dfs(n, left, rigth, "", res);

        return res;
        // write code here
    }

    private void dfs(int n, int left, int right, String str, ArrayList<String> res) {
        //终止条件 左边括号<右边括号
        if (right > left) {
            return;
        }

        //如果左边括号等于右边括号等于n则终止递归
        if (left == right && left == n) {
            res.add(str);
            return;
        }

        if (left < n) {
            dfs(n, left + 1, right, str + "(", res);
        }

        if (right < left) {
            dfs(n, left, right + 1, str + ")", res);
        }
    }
}
